# Python3 implementation of the approach

class knapsackCls:

    V_SUM_MAX = 1000
    N_MAX = 100
    #W_MAX = 10000000
    W_MAX = 1000
    _counter=0

    def __init__(self):
       self.dp = [[ 0 for i in range(self.N_MAX)] 
                  for i in range(self.V_SUM_MAX + 1)]
       self.v = [[ 0 for i in range(self.N_MAX)] 
                 for i in range(self.V_SUM_MAX + 1)] 
  
# Function to solve the recurrence relation 
    def solveDp(self,r, i, w, val, n,counter): 
        self._counter+=1
       
    ##    print(counter)
    ##    print('r',r)
    ##    print('i',i)
        #print("try") 
        # Base cases 
        if (r <= 0): 
            return 0
        if (i == n): 
            return self.W_MAX 
        if (self.v[r][i]): 
            return self.dp[r][i] 
      
        # Marking state as solved 
        self.v[r][i] = 1
      
        # Recurrence relation 
        self.dp[r][i] = min(self.solveDp(r, i + 1, w, val, n,counter),  
                w[i] + self.solveDp(r - val[i], i + 1, 
                                w, val, n,counter))

        #print("try") 
        return self.dp[r][i] 
  
    # Function to return the maximum weight 
    def maxWeight( self,w, val, n, c,counter): 
      
        # Iterating through all possible values 
        # to find the the largest value that can 
        # be represented by the given weights

        i=0
        for i in range(self.V_SUM_MAX, -1, -1): 
            if (self.solveDp(i, 0, w, val, n,counter) <= c):
                print('i is ',i)
                return i 

      
        return 0



    def sumTotalVal(self,valArr):
        sum=0
        for v in valArr:
            sum+=v

        return sum
        
# Driver code 
#if __name__ == '__main__':

oKS=knapsackCls()
w =   [3, 4, 5, 2, 2,5,3] 
val = [30, 50, 60,60,60,80,100]
n = len(w) 
C = 3
counter=0

totalVal=oKS.sumTotalVal(val)
oKS.V_SUM_MAX=totalVal

print('total Val(max) is ',oKS.V_SUM_MAX)

print('max weight is ',oKS.maxWeight(w, val, n, C,counter))
print('tried',oKS._counter,' times')
  
# This code is contributed by Mohit Kumar 
